#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int HPDataType;
typedef struct HeapNode
{
    HPDataType* a; // 数组
    int size;
    int capacity;
}HN;

void swap(HPDataType* a, HPDataType* b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}
// 初始化函数
void HeapInit(HN* hp)
{
    assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

// 向上调整函数
void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        // 向上调整的逻辑是当孩子小于父亲时，进行交换，然后继续向上调整
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            // 更新父子的值
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// 插入函数
void HeapPush(HN* hp, HPDataType x)
{
    assert(hp);
    if (hp->size == hp->capacity)
    {
        int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
        HPDataType* newnode = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
        if (newnode == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        hp->a = newnode;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size] = x;
    hp->size++;
    AdjustUp(hp->a, hp->size - 1);
}


// 向下调整函数
// 逻辑是找到两个孩子中较小的一个，当child < parent时进行交换
void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = 2 * parent + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child])
        {
            child++;
        }
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            // 交换后，继续向下调整
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapPop(HN* hp)
{
    assert(hp);
    assert(hp->a);
    swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;
    AdjustDown(hp->a, hp->size, 0);
}

HPDataType HeapTop(HN* hp)
{
    assert(hp->size > 0);
    return hp->a[0];
}

void HeapDestroy(HN* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->capacity = hp->size = 0;
}

int HeapEmpty(HN* hp)
{
    assert(hp);
    return hp->size == 0;
}

void HeapPrint(HN* hp)
{
    for (int i = 0; i < hp->size; i++)
    {
        printf("%d ", hp->a[i]);
    }
    printf("\n");
}

int HeapSize(HN* hp)
{
    return hp->size;
}